/******************************************************************************
 * \brief	双向链表（不直接包含数据）
 * \details	约定链表入口地址本身是尾(最后弹出)地址，head->next是头(最先弹出)地址；
 *			链表入口地址本身是无效的节点，即使弹出所有的节点，也只弹到入口之前
 *			的节点为止；
 *			一个双向链表实际上就是一个最简单的FIFO，就一个先进先出功能
 * \note	File format: UTF-8，中文编码：UTF-8；
 *			本链表不包含具体的数据，数据须在包含本链表成员的上层结构体中进行操作，
 *			也就是说本链表不能单独使用，必须和上层模块联用；
 *			本模块当前必须在gcc中才能编译通过，在msvc中不行，要想在Windows中使用
 *			需要去除typeof关键字，并在参数中增加一个变量；
 * \remarks	基于linux_6.1-rc4\scripts\kconfig\list.h，
 *			该源文件是从include\linux\list.h简化而来；
 *			Linux kernel源码中其它可供参考的链表还有：
 *			linux_6.1-rc4\scripts\kconfig\list.h  最好用
 *			linux_6.1-rc4\tools\usb\usbip\libsrc\list.h  可用
 *			linux_6.1-rc4\scripts\mod\list.h  可用
 *			linux_6.1-rc4\tools\firewire\list.h  另一种写法
 *			linux_6.1-rc4\tools\include\linux\list.h  太全
 *			linux_6.1-rc4\include\linux\list.h  最全
 * \author	中文注释：将狼才鲸
 * \date	2023-03-05
 ******************************************************************************/

#ifndef LIST_H
#define LIST_H

/*********************************** 头文件 ***********************************/
#include <stddef.h>	/* offsetof size_t */

/********************************** 结构定义 **********************************/
/**
 * \brief	双向链表结构体
 */
typedef struct list_head {
	struct list_head *next, *prev;
} list_head_t;

/********************************* 宏定义函数 *********************************/
/**
 * \brief	定义一个链表节点并赋初值，只是简化写法
 * \details	这个接口一般用不到，实际使用时会用init_list_head()
 * \param	name:	要定义的链表节点名
 */
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name)	\
	struct list_head name = LIST_HEAD_INIT(name)

/** 为链表的实际应用留下扩展接口 */

/**
 * \brief	获取一个结构体中的某个成员相对于结构体首地址的偏移量
 * \details	用于操作链表上层的带有有效数据+链表成员的结构体
 * \remarks	在stddef.h中已有该宏定义函数
 * \param	TYPE:	上层结构体名称
 * \param	MEMBER:	结构体中要查找偏移量的成员，一般这个成员是链表结构体指针
 * \return	结构体成员相对于结构体首地址的偏移量
 */
#undef offsetof
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

/**
 * \brief	从结构体中某一成员地址逆推出该结构体的首地址
 * \details	用于操作链表上层的带有有效数据+链表成员的结构体
 * \note	typeof是Linux GNU C(GCC)中扩展的关键字，从定义的变量名逆推出该变量的
 *			类型，如int a; typeof(a) b;中的第二句与int b;的效果相同；
 *			在Windows等其它编译器中编译会不通过；
 *			原始定义在include/linux/kernel.h中
 * \param	ptr:	需要逆推的上层结构体中的某个成员地址，一般是链表成员的地址
 * \param	type:	上层结构体的类型名，一般该类型是结构体
 * \param	member:	上层结构体中成员地址的名称，也就是a.b或a->b里面的这个b
 */
#define container_of(ptr, type, member) ({					\
	const typeof( ((type *)0)->member ) *__mptr = (ptr);	\
	(type *)( (char *)__mptr - offsetof(type,member) );})

/**
 * \brief	获取已嵌入链表结构体的上层结构体地址
 * \param	ptr:	上层结构体中的&struct list_head指针
 * \param	type:	嵌入了list_head成员的上层结构体类型名
 * \param	member:	上层结构体中list_head所属的名称
 */
#define list_entry(ptr, type, member)	\
	container_of(ptr, type, member)

/**
 * \brief	获取链表入口所在链表第一个元素对应的上层结构体地址
 * \note	调用前必须确保该链表非空
 * \param	ptr:	上层结构体中的&struct list_head指针，该指针是个链表入口
 * \param	type:	嵌入了list_head成员的上层结构体类型名
 * \param	member:	上层结构体中list_head所属的名称
 */
#define list_first_entry(ptr, type, member) \
	list_entry((ptr)->next, type, member)

/**
 * \brief	循环整个链表时的for(;x;x)语句（循环时不能删除当前链表节点）
 * \param	pos:	当前循环到的节点，是个临时变量
 * \param	head:	链表入口
 */
#define list_for_each(pos, head)	\
	for (pos = (head)->next; pos != (head); pos = pos->next)

/**
 * \brief	循环整个链表时的for(;x;x)语句（循环时可以删除当前链表节点）
 * \param	pos:	当前循环到的节点，是个临时变量
 * \param	n:		作为临时变量的节点
 * \param	head:	链表入口
 */
#define list_for_each_safe(pos, n, head)					\
	for (pos = (head)->next, n = pos->next; pos != (head);	\
		pos = n, n = pos->next)

/**
 * \brief	在上层结构体的基础上循环整个链表时的for(;x;x)语句（循环时不能删除当前链表节点）
 * \details	虽然是在上层带有效数据的结构体指针上进行循环，但是实际实现时
 *			是以其中的链表结构体作为依据
 * \param	pos:	要循环的上层结构体临时变量，该结构体中带有链表成员，
 *					pos值用作变量，本身不必预先赋值，但是循环时不能删除它
 * \param	head:	上层结构体中的list_head成员的地址
 * \param	member:	上层结构体中的list_head成员的名称
 * \note	head虽然是链表入口地址，但本身是尾(最后弹出)地址，head->next是头(最先弹出)地址；
 */
#define list_for_each_entry(pos, head, member)					\
	for (pos = list_entry((head)->next, typeof(*pos), member);	\
	     &pos->member != (head);								\
	     pos = list_entry(pos->member.next, typeof(*pos), member))

/**
 * \brief	在上层结构体的基础上循环整个链表时的for(;x;x)语句（支持循环时删除当前链表节点）
 * \details	虽然是在上层带有效数据的结构体指针上进行循环，但是实际实现时
 *			是以其中的链表结构体作为依据
 * \param	pos:	要循环的上层结构体临时变量，该结构体中带有链表成员，
 *					pos值用作变量，本身不必预先赋值，循环时可以删除它
 * \param	n:		上层结构体临时变量
 * \param	head:	上层结构体中的list_head成员的地址
 * \param	member:	上层结构体中的list_head成员的名称
 * \note	head虽然是链表入口地址，但本身是尾(最后弹出)地址，head->next是头(最先弹出)地址；
 */
#define list_for_each_entry_safe(pos, n, head, member)			\
	for (pos = list_entry((head)->next, typeof(*pos), member),	\
		 n = list_entry(pos->member.next, typeof(*pos), member);\
	     &pos->member != (head);								\
	     pos = n, n = list_entry(n->member.next, typeof(*n), member))

/* 因为下面都是内联函数，所以无需放在.c中，放在.h中即可，编译时不会
   重复编译，而是会像宏定义一样内联展开*/

/********************************** 私有函数 **********************************/
/**
 * \brief	在链表序列中插入一个链表节点（已知要插入位置的之前和之后的节点）
 * \param	_new:	要插入的链表节点
 * \param	prev:	插入点前方的链表节点
 * \param	next:	插入点后方的链表节点
 */
static inline void __list_add(struct list_head *_new,
			      struct list_head *prev,
			      struct list_head *next)
{
	next->prev = _new;
	_new->next = next;
	_new->prev = prev;
	prev->next = _new;
}

/**
 * \brief	在链表序列中删除一个链表节点（已知要删除位置的之前和之后的节点）
 * \param	prev:	删除点前方的链表节点
 * \param	next:	删除点后方的链表节点
 */
static inline void __list_del(struct list_head *prev, struct list_head *next)
{
	next->prev = prev;
	prev->next = next;
}

/**
 * \brief	在链表序列中删除一个链表入口节点
 * \param	entry:	要删除的链表节点
 */
static inline void __list_del_entry(struct list_head *entry)
{
	__list_del(entry->prev, entry->next);
}

/********************************** 接口函数 **********************************/
/**
 * \brief	初始化一个链表节点
 * \param	list:	要初始化的链表指针
 */
static inline void init_list_head(struct list_head *list)
{
	list->next = list;
	list->prev = list;
}

/**
 * \brief	在链表序列中删除一个链表入口节点，并重新初始化这个链表入口
 * \param	entry:	要删除的链表节点
 */
static inline void list_del_init(struct list_head *entry)
{
	__list_del_entry(entry);
	init_list_head(entry);
}

/**
 * \brief	判断链表是否为空
 * \param	head:	要判断的链表指针
 */
static inline int list_empty(const struct list_head *head)
{
	return head->next == head;
}

/**
 * \brief	判断链表是否为空（在多核CPU上较安全）
 * \param	head:	要判断的链表指针
 * \return	为空时返回真，不为空返回假
 */
static inline int list_empty_careful(const struct list_head *head)
{
	struct list_head *next = head->next;
	return (next == head) && (next == head->prev);
}

/**
 * \brief	将一个链表节点插入到一条链表的头部，先入后出
 * \param	new:	要插入的链表节点
 * \param	head:	要加入的那条链表的链表入口
 *					（链表入口所属的那个节点是链表尾，head->next是链表头）
 */
static inline void list_add(struct list_head *new, struct list_head *head)
{
	__list_add(new, head, head->next);
}

/**
 * \brief	将一个链表节点插入到链表尾，先入先出
 * \details	也就是更新了这条链表入口节点的前一个（入口并不是链表头）
 * \param	_new:	要插入的链表节点
 * \param	head:	要加入的那条链表的链表入口
 *					（链表入口所属的那个节点是链表尾，head->next是链表头）
 */
static inline void list_add_tail(struct list_head *_new, struct list_head *head)
{
	__list_add(_new, head->prev, head);
}

/* 用于让销毁的链表节点指向一个未使用地址 */
#define LIST_POISON	((void *)0x0)

/**
 * \brief	将一个链表节点从它自己所属的这条链表中删除
 * \param	entry:	要删除的链表节点
 */
static inline void list_del(struct list_head *entry)
{
	__list_del(entry->prev, entry->next);
	entry->next = (struct list_head *)LIST_POISON;
	entry->prev = (struct list_head *)LIST_POISON;
}

#endif /* LIST_H */

/*********************************** 文件尾 ***********************************/
